package pers.qianyu.month_202012.date_20201207.sliding_window;

/**
 * 567. 字符串的排列
 * https://leetcode-cn.com/problems/permutation-in-string/
 *
 * @author mizzle rain
 * @date 2020-12-07 17:31
 */
public class CheckInclusion {
    /**
     * 这种方法属于复杂的方法，其实不用这么麻烦
     * 直接固定滑动窗口的长度即可
     */
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        int[] need = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            need[s1.charAt(i) - 'a']++;
        }
        int needLen = 0;
        for (int i = 0; i < need.length; i++) {
            if (need[i] > 0) {
                needLen++;
            }
        }
        int[] window = new int[26];
        int left = 0, right = 0;
        int valid = 0;
        while (right < s2.length()) {
            char c1 = s2.charAt(right);
            window[c1 - 'a']++;
            if (need[c1 - 'a'] == window[c1 - 'a']) {
                valid++;
            }
            right++;
            while (valid == needLen) {
                if (right - left == s1.length()) {
                    return true;
                }
                char c2 = s2.charAt(left);
                if (need[c2 - 'a'] == window[c2 - 'a']) {
                    valid--;
                }
                window[c2 - 'a']--;
                left++;
            }
        }
        return false;
    }
}
